package 动态规划;
/**
 * 好题
 * 到后面 一步步 去优化 一下 这个题
https://leetcode.cn/problems/count-special-quadruplets/solution/gong-shui-san-xie-yi-ti-si-jie-mei-ju-ha-gmhv/
 这个 题 不仅 可以 学到 逐步  优化问题 还可以对 dp 有一个学习
 这个题 好题 好题	
 */

public class leetcode1995数据范围的不同难度的不同 {
	public static void main(String []args) {
		int nums[] = {1,2,3,6};
//		int nums [] = {1,1,1,3,5};
		System.out.println(solution(nums));
	}
	/**
	 * 首先  数组的 长度   nums.length <= 50
	 * 这就说明 这个题 是可以暴力过的
	 * 如果 数据 范围 扩大的 话 四层 暴力 for 循环  就必会 超时
	 * 这就在 引导 着 去做 一步步的  优化
	 * 下面 就是 超级 暴力 直接 O(n ^ 4) 时间复杂度
	 * 能过 仅仅 是因为  数据 规模小
	 */
	static int solution(int nums[]) {
		int ans = 0;
		int len = nums.length;
		for(int i = 0; i < len ;i++) {
			for(int j = i + 1; j < len ;j++) {
				for(int k = j + 1;k < len ;k++) {
					for(int l = k + 1 ;l < len ;l++) {
						if(nums[i] + nums[j] + nums[k] == nums[l])
							ans++;
					}
				}
			}
		}
//		return ans == 0 ? -1 : ans;
		return ans;
	}
}
